Nombre de parties d'un ensemble fini

Propriété

Soit \(E\) un ensemble fini à \(n\) éléments.
Le nombre de parties (de sous-ensembles) de \(E\) est \(2^n\) .

Démonstration

On considère \(E\) un ensemble fini à \(n\) éléments. On cherche à former une partie d'éléments de \(E\) .
Pour former une telle partie, on a deux choix pour chaque élément de \(E\) : l'incorporer dans la partie ou non.

Cela revient à choisir, pour chaque élément de \(E\) , un élément dans l'ensemble  \(\{ 0~;~ 1 \}\) .
Autrement dit, on associe à une partie de \(E\) une liste à \(n\) éléments formés par des \(0\) et des \(1\) .

Pour chacun de ces éléments de la liste, il y a deux possibilités.
Le nombre de parties (de sous-ensembles) d'un ensemble à \(n\) éléments est égal au nombre de \(n\) -uplets de l'ensemble \(\{ 0~ ;~ 1 \}\) c'est-à-dire \(2^n\) .